The present invention relates to a method and program for realistically animating the motion and interaction of rigid bodies in a display system. More particularly, the present invention relates to a method and program for solving a class of Linear Complementary Problems (LCPs) that arise during operation of a rigid body dynamics engine within the display system. The present invention finds application within conventional display systems, as well as within recently proposed display systems incorporating a hardware-based, physics processing unit.
Physics-based “animations” and “simulations” (hereafter these terms are used interchangeably regardless of application, specific method of display, or means of communicating related physics-based data) have been extensively investigated during the past three decades. Such animations are useful in a range of applications including virtual reality, electronic/computer games, scientific simulations, and robotic motion planning. Game developers, for example, increasingly use real-time, physics-based animations to enhance the realism of game object interactivity. Integral to the development of real-time, physics-based animations is the dynamic simulation of rigid body movements and interactions.
The term “rigid body” is used to describe animated objects that do not deform. They are said to be stiff even when colliding with other objects or with the environment defined by the animation. A rigid body simulation involves a complex sequence of computational steps causing animated bodies and related forces to interact in a realistic manner according to a set of defined physical rules, or so-called “constraints.” One goal of a rigid body simulator is to minimize or prevent the penetration of objects. If a simulator were to allow large penetrations of objects, then the illusion of object rigidity would be lost.
The practical development of physics-based animations, including rigid body simulations, has proved quite difficult. For simple cases, continuous real life problems can be written using continuous mathematics and solved algebraically. This approach is to high school physics students. However, the set of cases which have algebraic solutions is very small and a rigid body simulator must be able to handle any configuration of contacting rigid bodies. For this reason, a discrete problem is chosen that approximates the continuous problem. A discrete problem can be represented with a finite amount of data and can be evaluated numerically (by a computer) at discrete time intervals. Given that frames of animation are only required at discrete time intervals, this is an acceptable limitation.
Selecting a discrete model that approximates a sufficiently large class of continuous problems and is solvable in real time by a computer is difficult. A poor choice of discrete model can result in behavior that diverges unacceptably from the original continuous problem. For example with a bad model, objects might jump around for no reason, penetrate unacceptably, fall through a floor, or fly off into infinity.
At least in the context of computer games, the accuracy of the discretization with respect to the continuous problem is not particularly important. This result arises because unlike simulations used in science and engineering, computer game simulations need not be predictive. Any plausible discrete model will do. However, although this relaxed requirement makes it easier to meet the real-time constraint, it unfortunately doesn't make the mathematics any easier.
Numerous issues must be addressed when building a display system adapted to run real-time, physics-based animations. For example, the geometry of objects plays an important role in determining the physics of motion, as well as the physics of contact between objects. An object may be a single rigid body such as a chair or house, or may consist of a number of connected (e.g., jointed) bodies, such as a human figure. Collision or contact between objects must be accurately determined. Solving the necessary equations of motion to realistically animate objects has proved to be a difficult problem since accuracy (i.e., realism) and computational speed are always at odds.
In addition to preventing object/object or object/environment penetration, a display system implementing rigid body simulation must also take various physical properties of the objects into account when determining their motion. An example of such a property is mass. Further, physics-based animations must faithfully track and account for forces, such as gravity, acting upon objects. A rigid body simulator, or “engine,” associated with the display system must also create the illusion that simulated objects have certain surface properties, such as friction.
As one might expect, the modeling and simulation of the complexities arising from varied object geometries, interacting objects and forces, and changing object constraints requires a great deal of sophisticated mathematics. However, the mathematics implicated in the present invention are conventional. That is, those of ordinary skill in the art will understand the mathematical bases upon which the present invention is predicated. It is neither appropriate nor required that this present description try to teach the entire body of implicated mathematics. Nevertheless, some discussion of a mathematical model is required in order to establish a common descriptive vocabulary for the teachings that follow.
The conventional resources typically available in a display system implementing physics-based animations are conceptually illustrated in FIG. 1. Within FIG. 1, resources primarily based in hardware are shown in solid outline while software resources are shown in dotted outline. Those of ordinary skill in the art will recognize that such hardware/software designations are relatively arbitrary. For example, computational logic may be fully implemented in software or hardwired into a logic device at a system designer's discretion. However, some logical distinction between hardware and software, as exemplified by current best practices, is useful in the description that follows.
In FIG. 1, a Central Processing Unit (CPU) 1, such as a Pentium® microprocessor, together with its associated drivers and internal memory, access data from an external memory 11, and/or one or more peripheral devices 13, typically including a display. The terms “internal” and “external” are used to generally differentiate between various memories in relation to the other computational components in a system. Such differentiation is clearly relative, since most internal memory can be turned into external memory and vice verses. Generally speaking, however, an internal memory will typically be co-located on the same chip as related computational component(s), while external memory will typically be implemented using a separate chip or chip set.
A main application 4 is resident in external memory 2 and/or peripheral 13 (e.g., a magnetic or optical disk, a solid-state memory device such as a PROM, EPROM, or EEPROM, a cartridge for a game console or similar device). Main program 4 typically uses one or more Application Programming Interfaces (APIs) to access blocks of specialty software associated with various program functions. An API is a well understood programming technique used to establish a lexicon of sorts by which one piece of software may “call” another piece of software. The term “call” as variously used hereafter broadly describes any interaction by which one piece of software causes the retrieval, storage, indexing, update, execution, etc., of another piece of software.
Data instructions, often in a prescribed packet form and referred to hereafter as “commands,” are generally used to initiate calls between one or more software or hardware components. Execution (i.e., “running”) of software, in any of its various forms including micro-code, occurs upon receipt of an appropriate command.
Conventional display systems implementing physic-based animations routinely include or incorporate by functional “call” a related piece(s) of specialty software referred to generically hereafter as a “physics engine.” A physics engine may be thought of as an operative collection of resources, including specialized software, implementing realistic, real-time (or near real-time) physics effects within a main application.
With the recent and growing appetite for realism, physics engines have been added to the program code implementing, for example, PC games. Indeed, a market has emerged directed to the development physics engines or so-called “physics middleware.” Companies like HAVOK, MathEngine, Criterion, and Meqon Research have developed specialty software that may be called by a main application to better incorporate natural looking, physics-based interactions into a main application.
Prior to the use of physics engines in games, objects were animated by hand. These animations were triggered in response to input from the user. For example, if the user pressed a punch key, the game would play a corresponding punch animation. If the user pressed the punch key while standing next to a pile of boxes, then an animation of the pile of boxes falling over might have been played. If the user pressed the punch key while standing next to a game character, an animation of that character falling to the floor might have been played.
Since the animated motion displayed by the game was specified by a set of “pre-drawn” animations, the punch, the falling boxes, and the falling character would each move in the same manner every time. As well as being quite boring for the user, the animation could not take into account the context of the action. For example, if the user pressed the punch key next to a wall, there would often be nothing to stop the player's arm going through the wall. If the user had previously parked a car behind the pile of boxes, the boxes would typically fall through the car. If the user punched a character next to a cliff, the punched character would typically fall flat and lie in midair over the cliff rather than falling over the cliff ledge.
These problems were overcome to a certain extent by limiting the actions of the user, for example by not giving the user a car to drive, not allowing the user to walk within arm's length of a wall and not allowing fights next to cliffs. These restrictions were often frustrating to the user. Another way around the problem was to simply generate outcome animations for every possible combination of user actions. However, as the number of possible user actions grows, the number of outcome animations outcomes also grows. Thus, as game complexity increases the cost associated with the development of multiple animations becomes prohibitive.
Games designed using only animation start with a completely restricted environment where nothing unscripted can happen. This completely restricted environment is gradually made more interactive as an animator produces more and more animations. In contrast, games designed using physics-based approaches start with the opposite point of view, namely objects initially have complete freedom of motion. The game designer then, for example, designs a solid environment and adds a constraint that objects can still move with complete freedom, except that they must not fall through the solid environment. In a physics-based game, there is no reason why the user can't be given a car, or be allowed to punch a person next to a cliff, so those constraints are never introduced. As the game design progresses, some additional constraints are added however, as most fun games have rules.
Rather than supplying a set of animations for each object, the game designer specifies a set of physical properties for the object such as mass, friction, and in some cases even elasticity. The physics engine then uses the laws of physics to move the objects as if they had these properties such that they don't violate the specified constraints. The designer of a game incorporating physics-based animation decides which forces and torques should be applied to the objects in response to the user's input.
Of necessity, physics engines include a rigid body dynamics engine adapted to calculate the movement of rigid bodies within an animation. As will be appreciated by those of ordinary skill in the art, a rigid body dynamics engine will typically form one aspect of a larger physics engine. The exact programming and/or resource boundaries between the rigid body dynamics engine and other effects engines within the physics engine are a matter of design choice, and it is expected that the rigid body dynamics engine will draw upon a library of functions and/or a pool of common resources provided by the physics engine and/or by the main application.
Unfortunately, contemporary physics engines have significant limitations as to the number of objects in an animated scene, and more particularly, the number of active (i.e., moving or interacting) objects. Realistic visual images of simulated physics interaction must account for constraints placed upon many or all of the objects. As noted above, a constraint is a restriction on the possible movement or interaction of an object (e.g., a door hinge, a knee joint, a dog on a leash). Increasing complexity of terrain geometry greatly increases the difficulty of simulating object interactions with the terrain. The complexity of collision detection and resolution also increases with the complexity of an object's surface geometry (i.e., its surface detail).
Along with an increasing number of active objects, cutting edge animations and simulations demand an increased number of forces being applied to the objects. These aggregate demands are further aggravated by the increasing number of “time steps” per second being used in animations (i.e., the frequency with which the animated world with all its objects and forces is updated in real time).
However, among the factors challenging the realistic, real-time animation of objects in a physics-based application, the definition and incorporation of constraints upon the animated rigid body objects has proved most difficult. Indeed, it the existence of numerous constraints that makes the underlying mathematical (numerical analysis) problem much more difficult to resolve, as compared with a simple application of Newton's laws of motion.
One relatively older, conventional approach, generally referred to as the “extended coordinates method,” to the problem of solving physics-based constraint problems expresses constraints using Lagrange multipliers that correspond to forces that effectively maintain the constraints within the animated world space. See, for example, R. Bazel and A. Barr “A modeling system based on dynamic constraints,” Proceedings in SIGGRAPH 1988, Vol. 22, pp. 179–188 (1988). In such an approach, the Lagrange multipliers result in a large number of variables being used—nearly doubling the variables otherwise required to describe the animation. This increase in constraint-related variables results in an eight-fold increase in the quantity of computational resources required to resolve the animation, as compared with a similar animation lacking constraints.
Performance of the early “constraint-based” approach to rigid body simulation was improved by the incorporation of mathematical techniques taking advantage of the “sparse” nature of the matrixes used to express animation objects, forces, and constraints. See, for example, C. Lubich et al., “Mexx—numerical software for the integration of constrained mechanical multi-body systems,” Technical Report SC92-12, Konrad-Zuse-Zentrum fur Informationstechnik, (1992).
Other approaches to physic-based, rigid body animation extended these constraint-base methods to handle contact between objects. Incorporating contact within an animation is typically done by formulating the constrained dynamics equations as a Linear Complementary Problem (LCP), which is essentially a problem of finding some solution to a linear system that satisfies certain inequality constraints. P. Lodestadt, “Mechanical systems of rigid bodies subject to unilateral constraints” SIAM Journal of Applied Mathematics, 42(2): 281–96 (1982), is exemplary of early papers expressing the contact problem as an LCP. D. Baraff, “Fast contact force computation for non-penetrating rigid bodies,” Proceedings of SIGGRAPH 1994, Vol. 28, pages 23–34 (1994), later explained the use of an LCP solving algorithm developed by R. W. Cottle and G. B. Dantzig in “Complementary pivot theory of mathematical programming,” Linear Algebra and Application, 1, (1968).
Early LCP methods proved unreliable because there was no guarantee of the existence of a solution in the presence of contact with Coulomb friction. Indeed, there are known configurations of rigid bodies for which no set of contact and friction forces satisfies all of the constraints. D. E. Stewart and J. C. Trinkle, “An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction,” International Journal of Numerical Methods Engineering, (1996), resolved this difficulty, at least in part, by proposing a scheme that combined acceleration-level LCP with time stepping to obtain an LCP expressed as velocity and impulse variables. This method guaranteed solvability for a larger class of LCPs, and was later modified by M. Anitescu and F. Potra, “Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementary problems,” Nonlinear Dynamics, 14:231–47 (1997). Both of these documents propose use of the Lemke algorithm to solve LCPs. However, both approaches are impractically slow for use within real-time animations and overly prone to large computational errors.
In a more recent work, U.S. patent application Ser. No. 2003/0 179 205 A1 published Sep. 25, 2003 in the name of Smith et al., a rigid body simulator is proposed in which LCPs are solved using Murty's algorithm applied to velocity and position parameters instead of an acceleration parameter. Smith et al. further propose the use of a semi-implicit integration step in which constraint forces are determined by ensuring that the first derivative of the constraint function is zero, as compared with previous approaches which held the second derivative to zero.
Yet, all of the foregoing approaches to the resolution of LCPs arising from consideration of systems containing constrained, rigid bodies remain unsuited for real-time applications, unless such systems are greatly restricted in size and/or complexity. The conventional approaches are simply too slow. This slowness generally results from the use inefficient computational methods and inappropriate data forms.